//
//  TreeFile.swift
//  PlayData
//
//  Created by 冯琰琰 on 2022/3/20.
//

import Foundation

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class TreeSolution {
    /**
     * 144. 二叉树的前序遍历
     */
    var preorder = [Int]()
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        preorderT(root)
        return preorder
    }
    
    func preorderT(_ root: TreeNode?) {
        if root == nil {
            return
        }
        preorder.append((root?.val)!)
        preorderT(root?.left)
        preorderT(root?.right)
    }
    
    /**
     * 145. 二叉树的后序遍历
     */
    var backRet = [Int]()
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        postorderTBack(root)
        return backRet
    }
    
    func postorderTBack(_ root: TreeNode?) {
        if root == nil {
            return
        }
        postorderTBack(root?.left)
        postorderTBack(root?.right)
        backRet.append((root?.val)!)
    }
    
    /**
     * 100. 相同的树
     */
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }
        if p?.val != q?.val {
            return false
        }
        return isSameTree(p?.left, q?.left) && isSameTree(p?.right, q?.right)
    }
    
    /**
     * 101. 对称二叉树
     */
    func isSymmetric(_ root: TreeNode?) -> Bool {
        return checkSymmetric(left: root?.left, right: root?.right)
    }
    
    func checkSymmetric(left: TreeNode?,right: TreeNode?) -> Bool{
        
        if left == nil && right == nil {
            return true
        }
        return left?.val == right?.val && checkSymmetric(left: left?.left, right: right?.right) && checkSymmetric(left: left?.right, right: right?.left)
    }
    
    /**
     * 102. 二叉树的层序遍历
     */
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        var ret = [[Int]]()
        if root == nil || root?.val == nil {
            return ret
        }
        
        var samRet = [TreeNode]()
        samRet.append(root!)
        
        while !samRet.isEmpty {
            
            var subRet = [Int]()
            let count = samRet.count
            for _ in 0..<count {
                let temp = samRet.removeFirst()
                subRet.append(temp.val)
                if temp.left != nil {
                    samRet.append(temp.left!)
                }
                if temp.right != nil {
                    samRet.append(temp.right!)
                }
            }
            ret.append(subRet)
        }
        return ret
    }

    
    /**
     * 107. 二叉树的层序遍历 II
     */
    
    func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
        var ret = [[Int]]()
        if root?.val == nil {
            return ret
        }
        var nodeArr = [TreeNode]()
        nodeArr.append(root!)
        while !nodeArr.isEmpty {
            var subRet = [Int]()
            let count = nodeArr.count
            for _ in 0..<count {
                let node = nodeArr.removeFirst()
                subRet.append(node.val)
                
                if node.left != nil {
                    nodeArr.append(node.left!)
                }
                if node.right != nil {
                    nodeArr.append(node.right!)
                }
            }
            ret.insert(subRet, at: 0)
        }
        return ret
    }
    
    /**
     * 103. 二叉树的锯齿形层序遍历
     */
    
    func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
        var ret = [[Int]]()
        if root?.val == nil {
            return ret
        }
        var nodeArr = [TreeNode]()
        nodeArr.append(root!)
        var front = true
        while !nodeArr.isEmpty {
            var subRet = [Int]()
            let count = nodeArr.count
            for i in 0..<count {
                let node = nodeArr.removeFirst() //front ? nodeArr.removeFirst() : nodeArr.remove(at: count - 1 - i)
                
                front ? subRet.append(node.val) : subRet.insert(node.val, at: 0)
                
                if node.left != nil {
                    nodeArr.append(node.left!)
                }
                if node.right != nil {
                    nodeArr.append(node.right!)
                }
            }
            front = !front
            ret.append(subRet)
        }
        return ret
    }
    
    func isSameTree2(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }
        if p?.val == q?.val {
            return isSameTree2(p?.left, q?.left) && isSameTree2(p?.right, q?.right)
        }
        return false
        
    }
    
    func maxDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        let leftDe = maxDepth(root?.left) + 1
        let rightDe = maxDepth(root?.right) + 1
        return max(leftDe, rightDe)
    }
    
    /**
     * 109. 有序链表转换二叉搜索树
     */
    func sortedListToBST(_ head: ListNode?) -> TreeNode? {
        return buildTree(top: head, bot: nil)
    }
    func buildTree(top: ListNode?, bot: ListNode?) -> TreeNode? {
        if top === bot {
            return nil
        }
        let center = getCenterNode(top: top, bot: bot)
        let treenodel = TreeNode()
        treenodel.val = center?.val ?? 0
        treenodel.left = buildTree(top: top, bot: center)
        treenodel.right = buildTree(top: center?.next, bot: bot)
        return treenodel
        
    }
    
    func getCenterNode(top: ListNode?, bot: ListNode?) -> ListNode? {
        var slow = top
        var quick = top
        while quick !== bot && quick?.next !== bot {
            slow = slow?.next
            quick = quick?.next?.next
        }
        return slow
    }
    
}
